package com.study;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-12 19:48
 * @version: 1.0
 * @description: 斐波那契数列
 **/
public class Fibonacci {
    public static void main(String[] args) {
        long time1 = System.currentTimeMillis();
        System.out.println(recursive(30));
        long time2 = System.currentTimeMillis();
        System.out.println(calculate(30));
        long time3 = System.currentTimeMillis();
        System.out.println((time2 - time1) +"::::" + (time3 - time2));
        System.out.println(twoPointIterate(30));
    }

    /**
     * 使用双指针迭代
     *      集合没有必要保存每一个下标值，只要保存最新两个数就可以了，其他历史数据属于无用数据
     * @param num
     * @return
     */
    private static int twoPointIterate(int num) {
        if (num == 0){
            return 0;
        }
        if (num == 1){
            return 1;
        }
        int low = 0,high = 1;
        int sum = 0;
        for (int i = 2; i <= num; i++) {
            sum = low + high;
            low = high;
            high = sum;
        }
        return sum;
    }
    private static int twoPointIterate1(int num){
        if (num ==0) return 0;
        if (num ==1) return 1;
        int low = 0,high = 1,sum = 0;
        for (int i = 2; i <= num; i++) {
            sum = low + high;
            low = high;
            high = sum;

        }
        return sum;
    }

    /**
     *  递归算法求斐波那契的时间复杂度是 2 的 n 次幂 fibonacci  recursive
     * @param num
     * @return
     */
    private static int recursive(int num) {
       if (num == 0){
           return 0;
       }
       if (num == 1){
           return 1;
       }
       return recursive(num - 1) + recursive(num - 2);
    }

    /**
     *  去重递归
     *      递归得出的具体数值先存到一个数组里，后面递归先到该数组中查一次，如果查到则不用递归，直接取值
     *  时间复杂度是 O(n) 空间复杂度也是 O(n)
     * @param num
     * @return
     */
    private static int calculate(int num) {
        int[] arr = new int[num + 1];
        return recur(arr,num - 1) + recur(arr,num - 2);
    }

    private static int recur(int[] arr, int num) {
        if (num == 0){
            return 0;
        }
        if (num == 1){
            return 1;
        }
        if (arr[num] != 0){
            return arr[num];
        }
        arr[num] = recur(arr,num - 1) + recur(arr,num - 2);
        return arr[num];
    }

}
